package com.awesome.javademo.algorithm.solution;

import com.awesome.javademo.algorithm.tree.bean.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Author: JfangZ
 * Email: zhangjingfang@jeejio.com
 * Date: 2021/3/5 13:01
 * Description:
 */

public class SolutionTreeNode {
    // 前序遍历
    // 递归
    // 时间复杂度O(n)
    // 空间复杂度O(n)
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root, res);
        return res;
    }

    public static void preorder(TreeNode root, List<Integer> res) {
        if (root == null) return;
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }

    // 中序遍历
    // 迭代
    // 时间复杂度O(n)
    // 空间复杂度O(n)
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    public static void inorder(TreeNode root, List<Integer> res) {
        if (root == null) return;
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }

    // 后序遍历
    // 迭代
    // 时间复杂度O(n)
    // 空间复杂度O(n)
    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    public static void postorder(TreeNode root, List<Integer> res) {
        if (root == null) return;
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }

    // 层序遍历
    // 时间复杂度O(n)
    // 空间复杂度O(n)
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null) new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0;
        while (!queue.isEmpty()) {
            level++;
            List<Integer> tempList = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode t = queue.poll();
                tempList.add(t.val);
                if (t.left != null)
                    queue.offer(t.left);
                if (t.right != null)
                    queue.offer(t.right);
            }
            if (level % 2 == 1) {
                int length = tempList.size();
                for (int i = 0; i < length / 2; i++) {
                    int temp = tempList.get(i);
                    tempList.set(i, tempList.get(length - 1 - i));
                    tempList.set(length - 1 - i, temp);
                }
            }
            res.add(tempList);
        }
        return res;
    }


    // 二叉树最大深度
    public static int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
    }


    // 验证二叉搜索树
    public static boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        // 左树的值小于根节点，右树的值大于根节点
        if (isValidBST(root.left) && isValidBST(root.right)
                && (root.left.val < root.val) && (root.right.val > root.val)) return true;
        return false;
    }


//    public static boolean ergodic(TreeNode root) {
//    }
}
/**
 * private void doTreeNode() {
 *         TreeNode root = new TreeNode();
 *         root.val = 3;
 *         TreeNode left = new TreeNode();
 *         left.val = 9;
 *         TreeNode right = new TreeNode();
 *         right.val = 20;
 *         TreeNode leftLeft = new TreeNode();
 *         leftLeft.val = 9;
 *         TreeNode leftLeftLeft = new TreeNode();
 *         leftLeftLeft.val = 9;
 *         TreeNode leftLeftRight = new TreeNode();
 *         leftLeftRight.val = 100;
 *         TreeNode rightLeft = new TreeNode();
 *         rightLeft.val = 15;
 *         TreeNode rightRight = new TreeNode();
 *         rightRight.val = 7;
 *         root.left = left;
 *         root.right = right;
 *         root.left.left = leftLeft;
 *         root.left.left.left = leftLeftLeft;
 *         root.left.left.right = leftLeftRight;
 *         root.right.left = rightLeft;
 *         root.right.right = rightRight;
 *         List<List<Integer>> lists = SolutionTreeNode.levelOrder(root);
 *         for (int i = 0; i < lists.size(); i++) {
 *             for (int j = 0; j < lists.get(i).size(); j++) {
 *                 ShowLogUtil.info("i=" + i + ",j=" + j + "," + lists.get(i).get(j));
 *             }
 *         }
 *
 *
 *         //        TreeNode root = new TreeNode();
 * //        root.val = 3;
 * //        TreeNode left = new TreeNode();
 * //        left.val = 9;
 * //        TreeNode right = new TreeNode();
 * //        right.val = 20;
 * //        root.left = left;
 * //        root.right = right;
 * //        TreeNode rightLeft = new TreeNode();
 * //        rightLeft.val = 15;
 * //        TreeNode rightRight = new TreeNode();
 * //        rightRight.val = 7;
 * //        root.right.left = rightLeft;
 * //        root.right.right = rightRight;
 *
 * //        List<List<Integer>> lists = SolutionTree.levelOrder(root);
 * //        for (int i = 0; i < lists.size(); i++) {
 * //            ShowLogUtil.info(" ");
 * //            for (int j = 0; j < lists.get(i).size(); j++) {
 * //                ShowLogUtil.info("i=" + i + ",j=" + j +","+ lists.get(i).get(j));
 * //            }
 * //        }
 *     }
 */
